Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Інститут прикладної математики та фундаментальних наук
Кафедра прикладної математики
Звіт
про виконання лабораторної роботи №2
на тему:
“Теорія графів ”
Виконала :
ст. гр. ПМ-21
Львів -2008
Теоретичні відомості:
Якщо в графі G(х) через позначити число дуг, що йдуть з вершини у вершину , то матриця А= {} з n – стрічками та n –стовпцями називається матрицею суміжності вершин графа G(x).
Heхай і відповідають матрицям суміжності та ,тоді матрці + відповідають граф G(х)= + , який отримується об’єднанням дуг графів та на цій же множині вершини .
Матриці суміжності відповідає мультиграф побудований таким чином : в вершину з вершини йде стільки дуг, скільки існує різних шляхів в з і складених із двох дуг, перша з яких належить графу , а друга .
Ранг елемента − параметр, що дозволяє розподілити елементи графа в порядку їх вагомості Вагомість елемента тут визначається лише кількістю зв’язків з даного елемента з іншими. Характеризуючи значимість елемента рангом − структурним параметром, можна сказати, зо чим більший ранг елемента , тим більше він зв’язаний з іншими елементами графа.
Правило Таррі.
Щоб знайти шлях із вершини в в симетричному (зв’язному ) графі G(х) , досить дотримуватись правила : ніколи не проходити двічі по одному і тому ж коридору і тому ж напрямку; знаходячись у вершині не вибирати того ребра ,яку привело у вершину в перший раз, якщо є можливість іншого вибору.
Транспортна сітка Т є сукупністю двох об’єктів:
Зв’язного графа G= (X,) з властивостями :
В графі відсутні петлі
В графі G існує одна і лише одна вершина така, що множина =Ǿ.
В графі G існує одна і лише одна вершина , така ,що множина =Ǿ.
Цілочисельною невід’ємною функцією С(u) , заданою на множині дуг графа G. Вершина називається входом сітки, вершина - виходом. Значення функції С(u) на дузі u називається пропускною здатністю дуги.
Нехай U- множина дуг, що заходять у вершину , U- множина дуг, що виходять з множини . Цілочисельна невід’ємна функція , задана на множині дуг графа G, називається потоком ,якщо вона задовольняє такі умови:
= (,)
С(u)
Величина - називаться величиною потоку і позначається .
Код програми:
#include<iostream.h>
#include<conio.h>
class dijkstra
{
private:
int graph[26][26];
int set[26],predecessor[26],mark[26],pathestimate[26];
int source,target;
int num_of_vertices;
public:
int minimum();
void read();
void initialize();
void printpath(int);
void algorithm();
void output();
};
void dijkstra::read()
{
num_of_vertices =26;
int myGraph[26][26]={
{0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,0,0,0,0},
{1,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1},
{0,1,0,0,0,0,1,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0},
{0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0},
{0,0,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{1,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0},
{0,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0},
{0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0},
{1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0},
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,...
